/**
 * @param {character[][]} board
 * @return {void} Do not return anything, modify board in-place instead.
 */
var solveSudoku = function (board) {
  // 寻找下一个空白格（值为'.'）
  const findEmpty = (board) => {
    for (let i = 0; i < 9; i++) {
      for (let j = 0; j < 9; j++) {
        if (board[i][j] === ".") {
          return [i, j]; // 返回行和列
        }
      }
    }
    return null; // 没有空白格了
  };

  // 检查在位置(row, col)放置数字num是否有效
  const isValid = (board, num, [row, col]) => {
    // 检查行
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === num) {
        return false;
      }
    }

    // 检查列
    for (let i = 0; i < 9; i++) {
      if (board[i][col] === num) {
        return false;
      }
    }

    // 检查3x3的子网格
    const boxX = Math.floor(col / 3);
    const boxY = Math.floor(row / 3);

    for (let i = boxY * 3; i < boxY * 3 + 3; i++) {
      for (let j = boxX * 3; j < boxX * 3 + 3; j++) {
        if (board[i][j] === num) {
          return false;
        }
      }
    }

    return true;
  };

  // 回溯算法求解
  const solve = () => {
    const empty = findEmpty(board);

    // 如果没有空白格，说明数独已解决
    if (!empty) {
      return true;
    }

    const [row, col] = empty;

    // 尝试填入1-9的数字
    for (let num = 1; num <= 9; num++) {
      const strNum = num.toString();
      if (isValid(board, strNum, [row, col])) {
        // 如果有效，就填入该数字
        board[row][col] = strNum;

        // 递归尝试解决剩余的数独
        if (solve()) {
          return true;
        }

        // 如果递归失败，回溯，恢复为空白格
        board[row][col] = ".";
      }
    }

    // 如果1-9都不能填入，说明当前路径错误，返回false
    return false;
  };

  // 开始求解
  solve();
};
